package com.itheima.leetcode.od.b.logicalsimulation;

import java.util.regex.Pattern;

/**
 * (B卷,200分)- 最长的完全交替连续方波信号（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 输入一串方波信号，求取最长的完全连续交替方波信号，并将其输出，
 * <p>
 * 如果有相同长度的交替方波信号，输出任一即可，
 * <p>
 * 方波信号高位用1标识，低位用0标识，如图：
 * <p>
 * <p>
 * <p>
 * 说明：
 * <p>
 * 一个完整的信号一定以0开始然后以0结尾，即010是一个完整信号，但101，1010，0101不是
 * <p>
 * 输入的一串方波信号是由一个或多个完整信号组成
 * <p>
 * 两个相邻信号之间可能有0个或多个低位，如0110010，011000010
 * <p>
 * 同一个信号中可以有连续的高位，如01110101011110001010，前14位是一个具有连续高位的信号
 * <p>
 * 完全连续交替方波是指10交替，如01010是完全连续交替方波，0110不是
 * <p>
 * 输入描述
 * <p>
 * 输入信号字符串（长度 >= 3 且 <= 1024）：
 * <p>
 * 0010101010110000101000010
 * <p>
 * 注：输入总是合法的，不用考虑异常情况
 * <p>
 * 输出描述
 * <p>
 * 输出最长的完全连续交替方波信号串：01010
 * <p>
 * 若不存在完全连续交替方波信号串，输出 -1。
 * <p>
 * 用例
 * <p>
 * 输入	00101010101100001010010
 * <p>
 * 输出	01010
 * <p>
 * 说明
 * <p>
 * 输入信号串中有三个信号：
 * <p>
 * 0 010101010110(第一个信号段)
 * <p>
 * 00 01010(第二个信号段)
 * <p>
 * 010(第三个信号段)
 * <p>
 * 第一个信号虽然有交替的方波信号段，但出现了11部分的连续高位，不算完全连续交替方波，
 * 在剩下的连续方波信号串中01010最长
 * <p>
 * 题目解析
 * <p>
 * 本题要求“最长的完全交替连续方波信号”，
 * <p>
 * 其中形成“完全交替连续方波信号”由两个要点：
 * <p>
 * “完全交替连续方波”：完全连续交替方波是指10交替
 * “信号”：一个完整的信号一定以0开始然后以0结尾
 * 因此，“完全交替连续方波信号”，可以有两种描述方式：
 * <p>
 * 一个以0开头，之后有一个或多个10的字符串，用正则表示的话，即为 ^0(10)+$
 * 开头是一个或多个01，结尾是0的字符串，用正则表示的话，即为 ^(01)+0$
 * 下面代码我们用了第二种描述方式的正则来判断一个字符串是否为“完全交替连续方波信号”
 * <p>
 * 题目中还描述：
 * <p>
 * 输入的一串方波信号是由一个或多个完整信号组成
 * <p>
 * 两个相邻信号之间可能有0个或多个低位
 * <p>
 * 因此，当遇到相邻的两个0时，就是出现的两个信号（输入总是合法的，不用考虑异常情况）
 * <p>
 * 另外，输入中的信号，不仅有可能是“完全交替信号”，也可能是“不完全交替信号”，如0110，是一个完整信号，但是是非完全交替信号。
 * <p>
 * 因此，我的解题思路如下，定义一个栈stack，然后遍历输入字符串的字符c：
 * <p>
 * 如果stack为空，则c直接压入stack
 * <p>
 * 如果stack不为空，假设stack栈顶字符为top
 * <p>
 * 如果c == '0'，且 top == '0'，则说明c可能是新信号组成，而stack中已保存的字符组成的字符串可能是一个完全交替信号，我们用之前的正则来验证即可，如果验证OK，则记录此完全交替信号的长度，和本身。完成记录后，清空stack，记录新信号的c。
 * <p>
 * 如果c == '0'，而 top == ‘1’，则c直接压入stack
 * <p>
 * 如果c == '1' ，则c直接压入satck
 */
public class LongestContinuousSquareWaveSignal {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();*/

        String s = "00101010101100001010010";

        System.out.println(getResult(s));
    }

    public static String getResult(String s) {
        Pattern reg = Pattern.compile("^(01)+0$");

        int maxLen = 0;
        String ans = "-1";

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '0') {
                if (sb.length() > 0 && sb.charAt(sb.length() - 1) == '0') {
                    if (reg.matcher(sb.toString()).find() && sb.length() > maxLen) {
                        maxLen = sb.length();
                        ans = sb.toString();
                    }
                    sb = new StringBuilder();
                }
            }

            sb.append(c);
        }

        if (sb.length() > 0) {
            if (reg.matcher(sb.toString()).find() && sb.length() > maxLen) {
                return sb.toString();
            }
        }

        return ans;
    }
}